# -*- coding: utf-8 -*-
# @Time: 2021/8/9 8:52
# @File: problem-17.py
# @DESC:
from typing import List


class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        map = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz',
        }
        res = []

        # 组合后的字符串，字母
        def back_track(combine_str, letters):
            if len(letters) == 0:
                res.append(combine_str)
            else:
                if letters[0] not in map:
                    back_track(combine_str + '', letters[1:])
                else:
                    for i in map[letters[0]]:
                        back_track(combine_str + i, letters[1:])

        if len(digits) > 0:
            back_track('', digits)

        return res


s = Solution()

res = s.letterCombinations("21")

print(res)
